1. Field of the Invention
This invention relates to a packet buffer device and a packet switching device that once store and then transfer input packets, and more particularly, to a packet buffer device and a packet switching device for realizing the function of delivering packets to a plurality of destinations.
2. Description of the Related Background Art
Japanese Patent Laid-Open Publication No. H 10-145387 discloses a packet buffer device in which the queue access throughput does not depend on the number of destinations. FIG. 8 is a block diagram showing a part of the interior structure of a packet switching device using a packet buffer device disclosed in that publication.
As shown in FIG. 8, formed inside the packet buffer device 100 are one or more packet queues 110 and one or more coupled packet queues 112. Which packet queue each input packet is stored in is determined based on the header of the packet. Each of packets stored in these packet queues 110 are outputted to one of output ports #1 through #4 via a bus 120 in accordance with an instruction from a scheduler (not shown), and then sent from the output port #1 through #4. In ATM (asynchronous transfer mode) communication, these packets are called ATM cells.
In the existing packet buffer device 100, its multi-casting function was realized by the process explained below. The “multi-casting function” herein pertains to a function of transferring common contents to a plurality of destinations.
FIG. 9 is a diagram that explains broadcasting packet processing for realizing a multi-casting function, which is executed inside the packet buffer device 100.
As shown in FIG. 9, packets introduced into a packet allocator 130 provided in the packet buffer device 100 are allotted based on headers contained in respective packets. In the case where these packets are broadcasting packets for realizing a multi-casting function, they are stored in corresponding one of the coupled packet queues 112 prepared for each flow.
The “flow” herein pertains to a set of packets composing a common multi-casting. For example, in FIG. 9, the coupled packet queue 112 (1) is a queue for the flow consisting of copy destinations CP1, CP2, CP3 and CP4, the coupled packet queue 112(2) is a queue for the flow consisting of copy destinations CP5 and CP6, and the couples packet queue 112(3) is a queue for the flow consisting of copy destinations CP7, CP8 and CP9. In this manner, in the packet buffer device 100, multi-casting trees corresponding to the number of flows concurrently exist, overlapping one another. Considering uni-casting as a particular multi-casting having only one destination, ordinary packet queue 110 can be regarded as a coupled packet queue 112.
Next taking the coupled packet queue 112(1) as an example, its operation is explained. As shown in FIG. 9, the packet allocator 130 analyzes the header of an inputted packet. Assuming that the inputted packet is one to be stored in the coupled packet queue 112(1), the packet allocator 130 inputs this packet as one element at the uppermost stream of the coupled packet queue 112(1). That is, the element is stored at the tail of the leaf queue LQ(1) of the copy destination CP1 in the coupled packet queue 112(1).
The packet stored at the tail of the leaf queue LQ(1) of the copy destination CP1 eventually comes to the leading head of the leaf queue LQ(1) of the copy destination CP1, and it is sent out from the output port as a packet for the copy destination CP1. The packet, sent out, is stored at the tail of the leaf queue LQ(2) of the copy destination CP2 in the coupled packet queue 112(1). Similarly, this packet eventually comes to the leading head of the leaf queue LQ(2) of the copy destination CP2, it is sent out from the output port as a packet for the copy destination CP2, and stored at the tail of the leaf queue LQ(3) of the copy destination CP3 in the coupled packet queue 112(1). By repeating these procedures, the packet is sent out also from the copy destinations CP3 and CP4, and removed from the coupled packet queue 112(1).
Thus, the existing packet buffer device 100 realized the multi-casting function by making individual leaf queues LQ for respective copy destinations forming respective flows in coupled packet queues 112 prepared for individual flows.
In this multi-casting function, however, it may be desirable or necessary to erase one or more copy destinations forming a flow, such as the case where a user doing a multi-casting communication finishes this multi-casting communication. In this case, the leaf queue LQ of the corresponding copy destination has to be deleted from the coupled packet queue 112.
Referring to FIG. 9, in case of deleting the copy destination CP2 from the coupled packet queue 112(1), the leaf queue LQ connected next to the leaf queue LQ(1) of the copy destination CP1 is changed from the leaf queue LQ(2) of the copy destination CP2 to the leaf queue LQ(3) of the copy destination CP3. That is, a packet sent out from the leaf queue LQ(1) of the copy destination CP1 is accumulated at the tails of the leaf queue LQ(3) of the copy destination CP3.
If any packet is accumulated in the leaf queue LQ(2) of the copy destination CP2, it is necessary to continue egress of packets from the leaf queue LQ(2) of the copy destination CP2 and accumulate the sent-out packets in the leaf queue LQ(3) of the copy destination CP3. In this manner, by evacuating all packets from the leaf queue LQ(2) to be deleted, the packet buffer device 100 maintained consistency inside.
The existing packet buffer device, however, involved the following problems.
First referring to FIG. 10, in the case where no packets have ever been accumulated in the next leaf queue LQ(n+1) upon deleting the leaf queue LQ(n), the header pointer of the leaf queue LQ(n+1) is still indefinite, and packets of the leaf queue LQ(n) cannot be changed to the leaf queue LQ(n+1).
This problem is explained below in greater detail with reference to FIG. 11. FIG. 11 is a diagram that shows elements P100 through P103 accumulated in the coupled packet queue 112, and (n−1)th through (n+1)th coupling management tables for managing the coupled packet queue 112.
As shown in FIG. 11, since no element has ever been accumulated in the leaf queue LQ(n+1), the head pointer H(n+1) of the (n+1)th leaf table is still indefinite. In ordinary operation not deleting the leaf queue LQ(n+1), since the head pointer H(n+1) points the element P100 upon transfer of the element P100 of the leaf queue LQ(n) to the leaf queue LQ(n+1), the head pointer H(n+1) is defined at that time. As a result, the element P100 heretofore located at the leading of the leaf queue LQ(n) becomes the tail element of the leaf queue LQ(n+1) (it is also the leading element because it is the only one element of the leaf queue LQ(n+1)). Further, the head pointer H(n) of the n-th leaf table for the leaf queue LQ(n) points the element P101.
On the other hand, in case of deleting the leaf queue LQ(n), he leaf queue LQ(n−1) executed the same processing to the leaf queue LQ(n+1). That is, upon transferring the element P102 from the leaf queue LQ(n−1) to the leaf queue LQ(n+1), the head pointer H(n+1) of the (n+1)th leaf table for the leaf queue LQ(n+1) points the element P102, and the head pointer H(n+1) is then determined. However, once the head pointer H(n+1) points the element P102 heretofore located at the leading of the leaf queue LQ(n−1), the elements P100 and P101 accumulated in the leaf queue LQ(n) cannot be transferred to the leaf queue LQ(n+1). That is, the elements P100 and P102 accumulated in the leaf queue LQ(n) cannot be coupled by using the head pointer H(n+1) and the inter-element link pointer.
Thus the existing packet buffer device 100 involved the problem that connection of packets of the leaf queue LQ(n) could not be changed to the leaf queue LQ(n+1) if no packets had ever been accumulated in the next leaf queue LQ(n+1) upon deleting the leaf queue LQ(n), because the head pointer of the leaf queue LQ(n+1) was not determined.
Second, as shown in FIG. 12, the existing packet buffer device had the problem that, upon deleting the leaf queue LQ(n) located at the downstream end of the coupled packet queue 112, when all of the upper-stream leaf queues LQ(1) through LQ(n−1) were empty, the tail pointer of the coupled packet queue 112 exhibited an abnormality.
This problem is explained below in greater detail with reference to FIG. 13. FIG. 13 is a diagram that shows elements P110 through P112 accumulated in the coupled packet queue 112, and coupling management tables and a root table for managing the coupled packet queue 112. As shown in FIG. 13, the tail pointer T provided in the root table points the element P112 at the tail of the coupled packet queue 112. If any element remains in the leaf queues LQ(1) through LQ(n−1) other than the leaf queue LQ(n) at the downstream end, the tail pointer T does not become indefinite, and no problem occurs.
If, however, the leaf queues LQ(1) through LQ(n−1) other than the leaf queue LQ(n) to be deleted have no accumulated elements, a problem occurs for the following reason. That is, in this case, the tail pointer T points the element “that was the tail” of the leaf queue LQ(n−1). This means that the tail pointer T points the element already released.
Under such condition, since the total information C in the root table of elements having been accumulated in the coupled packet queue 112 is not zero, the packet buffer device 100 cannot recognize that the tail pointer T is currently indefinite. Therefore, the packet buffer device 100 results in linking a packet newly arriving packet at the coupled packet queue 112 to the element pointed by the tail pointer T. In other words, the device 100 links the new packet to the element already released. Linking the packet in this manner, two links are formed for a single element, i.e. the link of the coupled packet queue 112 and the link of the released list. Therefore, if the element is re-used for linkage of another element, the linked element is destroyed. Even when it has not been used heretofore, it will be re-used eventually, the link currently using the element that was once released will be destroyed.
Thus, the existing packet buffer device 100 had the problem that, when elements remained only in the leaf queue LQ(n) and the leaf queue LQ(n) was deleted, the packet buffer device 100 erroneously recognized that the tail pointer was definite even though no elements actually remained.
Moreover, the situations as shown in FIGS. 10 and 12 can often occur when there is any trouble in the output of the copy destination to be deleted, because elements cannot be sent out to that copy destination.